﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Brainee.Search
{
  /// <summary>
  /// </summary>
  /// <remarks>
  /// </remarks>
  public class BestFirstStrategy : ISearchStrategy
  {
#region SearchState instances comparer

    private class SearchStateComparer : IComparer<ISearchState>
    {
      private Func<ISearchState, double> _heuristic;

      public SearchStateComparer (Func<ISearchState, double> heuristic)
      {
        _heuristic = heuristic;
      }

      public int Compare (ISearchState x, ISearchState y)
      {
        double valueX = _heuristic (x);
        double valueY = _heuristic (y);

        if (valueX < valueY) return -1;
        if (valueX > valueY) return 1;
        return 0;
      }
    }

#endregion
#region Fields

    private readonly SearchStateComparer _comparer;

    private SortedSet<ISearchState> _fringe;

#endregion
#region Constructor

    public BestFirstStrategy (Func<ISearchState, double> heuristic)
    {
      _comparer = new SearchStateComparer (heuristic);
    }

#endregion
    #region Strategy definition

    /// <summary>
    /// Initialize the strategy internals with the specified problem.
    /// </summary>
    /// <param name="problem">The problem to solve with this strategy.</param>
    public void Initialize (IProblem problem)
    {
      if (problem == null)
        throw new ArgumentNullException ("problem");

      _fringe = new SortedSet<ISearchState> (_comparer);
      _fringe.Add (new SearchState (problem.InitialState));
    }

    /// <summary>
    /// Test if there are unexplored search states.
    /// </summary>
    /// <returns>false if there is at least one state that can be explored; otherwise, true</returns>
    public bool HasUnexploredStates ()
    {
      if (_fringe == null)
        throw new InvalidOperationException ("The strategy is not correctly initialized.");

      return _fringe.Count > 0;
    }

    /// <summary>
    /// Get the next unexplored state.
    /// </summary>
    /// <returns>An unexplored search state</returns>
    public ISearchState NextState ()
    {
      if (_fringe == null)
        throw new InvalidOperationException ("The strategy is not correctly initialized.");

      if (!HasUnexploredStates ())
        return null;

      ISearchState next = _fringe.Min;
      /*_fringe =*/ _fringe.Remove (next);

      return next;
    }

    /// <summary>
    /// Expands the specified state
    /// </summary>
    /// <param name="state">The state to expand</param>
    /// <param name="problem">The problem to solve</param>
    public void Expand (ISearchState state, IProblem problem)
    {
      if (_fringe == null)
        throw new InvalidOperationException ("The strategy is not correctly initialized.");
      if (state == null)
        throw new ArgumentNullException ("state");
      if (problem == null)
        throw new ArgumentNullException ("problem");

      foreach (ActionState pair in problem.Successors (state.State))
      {
        /*_fringe =*/ _fringe.Add (new SearchState (
          pair.State,
          state,
          pair.Action,
          state.PathCost + problem.StepCost (state.State, pair.Action, pair.State),
          state.Depth + 1));
      }
    }

#endregion
  }
}
